package com.zlp.partice;

import org.junit.Test;
import org.w3c.dom.Node;

import java.math.BigInteger;
import java.util.*;

import static com.google.common.math.LongMath.isPrime;

/**
 * @author: zhulaiping
 * @time: 2022/5/3 9:48
 */
public class Day20220503 {

    public String[] reorderLogFiles(String[] logs) {
        List<String> letterLogs = new ArrayList<>();
        List<String> numLogs = new ArrayList<>();
        for (int i=0;i<logs.length;i++){
           String cur = logs[i].substring(logs[i].indexOf(' '));
           if(Character.isDigit(cur.charAt(0))){
               numLogs.add(logs[i]);
           }else{
               letterLogs.add(logs[i]);
           }
        }
        Collections.sort(letterLogs,(o1, o2) -> {
            String s1 = o1.substring(o1.indexOf(' '));
            String s2 = o2.substring(o2.indexOf(' '));
            if(!s1.equals(s2)){
                return s1.compareTo(s2);
            }else {
                return o1.substring(0,o1.indexOf(' ')).compareTo(o2.substring(0,o2.indexOf(' ')));
            }
        });
        System.out.println(numLogs);
        System.out.println(letterLogs);
        letterLogs.addAll(numLogs);
        return letterLogs.toArray(new String[letterLogs.size()]);
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list = new ArrayList<>();
        LinkedList<Integer> queue1 = new LinkedList();
        LinkedList<Integer> queue2 = new LinkedList();
        dfs1(root1,queue1);
        dfs1(root2,queue2);
        System.out.println(queue1);
        System.out.println(queue2);
        while (queue1.size()>0 && queue2.size()>0){
            list.add(queue1.peekLast()>queue2.peekLast()?queue2.poll():queue1.poll());
        }
        while (queue1.size()>0) list.add(queue1.pop());
        while (queue2.size()>0) list.add(queue2.pop());
        return list;
    }
    private void dfs1(TreeNode root, Deque queue) {
        if(root == null) return;
        dfs1(root.left, queue);
        queue.offer(root.val);
        dfs1(root.right, queue);
    }

    public int findTheWinner(int n, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i=1;i<=n;i++){
            queue.offer(i);
        }
        int sum = 1;
        while (queue.size()>1){
            Integer poll = queue.poll();
            if(sum == k){
                sum = 1;
            }else{
                queue.offer(poll);
                sum++;
            }
        }
        return queue.peek();
    }

    public int smallestRangeI(int[] nums, int k) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        return min + k >= max + k ? 0 : max - min - 2 * k;
    }


    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k <= 1) return 0;
        int l = 0,r = 0, product = 1,res = 0;
        for (;r<nums.length;r++){
            product *= nums[r];
            while (product>=k && l<=r){
                product /= nums[l++];
            }
            res += r-l+1;
        }
        return res;
    }

    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    };




    // 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
    public Node construct(int[][] grid) {
        return dfs(0,grid[0].length,0,grid.length,grid);
    }

    private Node dfs(int i, int row, int j, int column,int[][] grid) {
        boolean equal = true;
        int curVal = grid[i][j];

        for (int curI = i;curI<row;curI++){
            for (int curJ = j;curJ<column;curJ++){
                if(grid[curI][curJ]!=curVal){
                    equal = false;
                    break;
                }
            }
            if(!equal) break;
        }
        if(equal){
            return new Node(grid[i][j]==1,true);
        } else {
            Node topLeft = dfs(i, (i + row) / 2, j, (j + column) / 2, grid);
            Node topRight = dfs(i, (i + row) / 2, (j + column) / 2, column, grid);
            Node bottomLeft = dfs((i + row) / 2, row, j, (j + column) / 2, grid);
            Node bottomRight = dfs((i + row) / 2, row, (j + column) / 2, column, grid);
            return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }

    LinkedList<Integer> list = new LinkedList<>();

    public int ping(int t) {
        list.offer(t);
        Integer curValue = t - 3000;
        while (list.peek() < curValue){
            list.poll();
        }
        return list.size();
    }
    public int[] sortArrayByParity(int[] nums) {
        int l = 0,r = nums.length-1;
        while (l<r){
            while (l<nums.length && nums[l] % 2 == 0) l++;
            if(l == nums.length) break;
            if(r>=0 && nums[r] % 2 == 1) r--;
            if(r<0) break;
            if(l<r) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
            l++;
            r--;
        }
        return nums;
    }

    public int minMutation(String start, String end, String[] bank) {
        if(start.equals(end)) return 0;
        LinkedList<String> queue = new LinkedList<>();
        queue.add(start);
        int path = 0;
        Set<String> set = new HashSet<>();
        set.add(start);
        while (queue.size()>0 && path<=bank.length){
            int curSize = queue.size();
            path++;
            for (int i=0;i<curSize;i++){
                String curStr = queue.poll();
                for (String str:bank){
                    if(isSuit(str,curStr)){
                        if(str.equals(end)) return path;
                        else {
                            if(!set.contains(str)){
                                set.add(str);
                                queue.add(str);
                            }
                        }
                    }
                }
            }
            System.out.println(queue);
        }
        return -1;
    }

    private boolean isSuit(String str, String curStr) {
        int res = 0;
        for (int i=0;i<8;i++){
            if(str.charAt(i)!=curStr.charAt(i)) res++;
        }
        return res == 1;
    }

    public List<Integer> findDuplicates(int[] nums) {
        for (int i=0;i<nums.length;i++){
            int index = nums[i] >=0?nums[i]:Math.abs(nums[i]);
            nums[index-1] = -nums[index-1];
        }
        List<Integer> res = new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            if(nums[i]>0) list.add(i+1);
        }
        return res;

    }

    public int[] diStringMatch(String s) {
        char[] chars = s.toCharArray();
        int[] res = new int[s.length() + 1];
        int l = 0, r = res.length, index = 0;
        for (int i = 0; i < chars.length; i++) {
            res[index++] = chars[i] == 'I' ? l++ : r--;
        }
        res[index] = l;
        return res;
    }


    class TreeNode2 {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode2(int x) { val = x; }
   }




    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder(root.val+",");
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size()>0){
            int size = queue.size();
            for (int i=0;i<size;i++){
                TreeNode node = queue.poll();
                sb.append(node.left==null?"*,":node.left+",");
                sb.append(node.right==null?"*,":node.right+",");
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
        }
        System.out.println(sb.toString());
        return sb.toString();
    }

    public String defangIPaddr(String address) {
        return address.replace(".","[.]");
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        return null;
    }
    int depth = Integer.MIN_VALUE,ret;
    public int findBottomLeftValue(TreeNode root) {
        dfs2(root,0);
        return ret;
    }

    private void dfs2(TreeNode root,int curDepth) {
        if(root == null) return;
        if(curDepth>depth){
            depth = curDepth;
            ret = root.val;
        }
        dfs2(root.left,curDepth+1);
        dfs2(root.right,curDepth+1);
    }

    public void wiggleSort(int[] ret) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
        for (int num:ret) queue.offer(num);
        for (int i=1;i<ret.length;i+=2){
            ret[i] = queue.poll();
        }
        for (int i=0;i<ret.length;i+=2){
            ret[i] = queue.poll();
        }
        return;
    }



    public int minDeletionSize(String[] strs) {
        int res = 0;
        for (int i = 0; i < strs[0].length(); i++) {
            boolean flag = true;
            for (int j = 0; j < strs.length - 1; j++) {
                if (strs[j].charAt(i) > strs[j + 1].charAt(i)) {
                    flag = false;
                    break;
                }
            }
            if(!flag) res++;
        }
        return res;
    }

    public boolean oneEditAway(String first, String second) {
        if(Math.abs(first.length()-second.length())>2) return false;
        int cnt = 0;
        if(first.length()==second.length()){
            for (int i=0;i<first.length();i++){
                if(first.charAt(i)!=second.charAt(i)) cnt++;
            }
            return cnt <= 1;
        }else{
            if(first.length()<second.length()){
                String temp = first;
                first = second;
                second = temp;
            }
            for (int i=0,j=0;i<first.length();i++,j++){
                if(first.charAt(i)!=second.charAt(j)){
                    if(first.charAt(i+1)!=second.charAt(j)) return false;
                    i++;
                    cnt++;
                }
            }
            return cnt<=1;
        }
    }





    public boolean isAlienSorted(String[] words, String order) {
        for (int i=0;i<words.length-1;i++){
            for(int j=i+1;j<words.length;j++){
                int cal = cal(words[i], words[j], order);
                if(cal==2) return false;
                if(cal==1) return true;
                if(words[i].length()>words[j].length()) return false;
            }
        }
        return true;
    }

    private int cal(String word, String word1,String order) {
        char[] chars = word.toCharArray();
        char[] chars1 = word1.toCharArray();
        for (int i=0;i<Math.min(word.length(),word1.length());i++){
            if(chars[i] == chars1[i]) continue;
            int a = 0,b = 0;
            for (int j=0;j<order.length();j++){
                if(order.charAt(j) == chars[i]) a = j;
                if(order.charAt(j) == chars1[i]) b = j;
            }
            return a < b ?1:2;
        }
        return 3;
    }

    public int[] findRightInterval(int[][] intervals) {
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < intervals.length; i++) {
            treeMap.put(intervals[i][0],i);
        }
        int[] result = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            Integer integer = treeMap.ceilingKey(intervals[i][1]);
            result[i] = integer == null ? -1 : treeMap.get(integer);
        }
        return result;
    }

    public int minMoves2(int[] nums) {
        int sum = 0;
        for (int val : nums) sum += val;
        int a = sum / nums.length, b = sum / nums.length + 1;
        int suma = 0, sumb = 0;
        for (int val : nums) {
            suma += Math.abs(a - val);
            sumb += Math.abs(a - val);
        }
        return Math.min(suma, sumb);
    }

    public int repeatedNTimes(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num:nums){
            if(set.contains(num)) return num;
            set.add(num);
        }
        return 0;
    }

    public int findSubstringInWraproundString(String p) {
        char[] chars = p.toCharArray();
        //每个值为该下标字符结尾的字串数量
        int[] pos = new int[26];
        pos[chars[0]-'a'] = 1;
        int cur = 1;
        for (int i=1;i<chars.length;i++){
            if(chars[i]-chars[i-1] != 1 && chars[i]-chars[i-1] != -25){
                cur = 1;
            }else{
                cur++;
            }
            int index = chars[i]-'a';
            pos[index] = Math.max(cur,pos[index]);
        }
        return Arrays.stream(pos).sum();
    }

    public List<Integer> fallingSquares(int[][] positions) {
        Integer[] ret = new Integer[positions.length];
        int max = Integer.MIN_VALUE;
        for (int i=0;i<positions.length;i++){
            int left = positions[i][0],right = left+positions[i][1],baseHeight = right;
           for (int j=0;j<i;j++){
               int left2 = positions[j][0],right2 = left2+positions[j][1];
               if(left<right2&&left>left2 || right<right2 && right>left2){
                   baseHeight = Math.max(baseHeight,baseHeight+right2);
               }
           }
           ret[i] = baseHeight;
        }
        for (int i=1;i<ret.length;i++){
            ret[i] = Math.max(ret[i],ret[i-1]);
        }
        return Arrays.asList(ret);
    }

    public int findClosest(String[] words, String word1, String word2) {
        TreeSet<Integer> set = new TreeSet<>();
        List<Integer> list = new ArrayList<>();
        for (int i=0;i< words.length;i++){
            if(words[i].equals(word1)){
                set.add(i);
            }
            if(words[i].equals(word2)){
                list.add(i);
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int val:list){
            Integer ceiling = set.ceiling(val);
            Integer floor = set.floor(val);
            if(ceiling != null) {
                ret = Math.min(ret,Math.abs(ceiling-val));
            }
            if(floor != null) {
                ret = Math.min(ret,Math.abs(floor-val));
            }
        }
        return ret;
    }
    public int findClosest2(String[] words, String word1, String word2) {
        int idx1 = 0,idx2 = 0,ret = 100000;
        for (int i=0;i< words.length;i++){
            if(words[i].equals(word1)){
                idx1 = i;
            }
            if(words[i].equals(word2)){
                idx2 = 2;
            }
            ret = Math.min(ret,Math.abs(idx1-idx2));
        }
        return ret;
    }

    public String removeOuterParentheses(String s) {
        StringBuilder ret = new StringBuilder();
        char[] chars = s.toCharArray();
        int pos = 0;
        for (int i = 0; i < chars.length; i++) {
            pos = chars[i] == '(' ? pos + 1 : pos - 1;
            if (pos ==0 || pos == 1 && chars[i] != '(') continue;
            ret.append(chars[i]);
        }
        return ret.toString();
    }

    public String validIPAddress(String queryIP) {
        return queryIP.contains(".") ? isIPV4(queryIP) : isIPV6(queryIP);
    }

    private String isIPV4(String queryIP) {
        if(queryIP.charAt(0) == '.'||queryIP.charAt(queryIP.length()-1) == '.')
            return "Neither";
        String[] split = queryIP.split("\\.");
        if(split.length != 4) return "Neither";
        for (String str:split){
            if(str.length()>1 && str.charAt(0) == '0') return "Neither";
            try {
                int i = Integer.parseInt(str);
                if(i<0 && i>255) return "Neither";
            }catch (Exception e){
                return "Neither";
            }
        }
        return "IPV4";
    }

    private String isIPV6(String queryIP) {
        if(queryIP.charAt(0) == ':'||queryIP.charAt(queryIP.length()-1) == ':')
            return "Neither";
        String[] split = queryIP.split(":");
        if(split.length != 8) return "Neither";
        for (String str:split){
            if(str.length()<1 || str.length()>4) return "Neither";
            try {
                BigInteger val = new BigInteger(str, 16);
                if(val.intValue()<0 && val.intValue()>65535) return "Neither";
            }catch (Exception e){
                return "Neither";
            }
        }
        return "IPV6";
    }

    public int sumRootToLeaf(TreeNode root) {
        return dfs2(0,root);
    }

    private int dfs2(int val,TreeNode root) {
        val = val * 2 + root.val;
        if (root.left == root.right) {
            return val;
        }
        int left = root.left == null ? 0 : dfs2(val, root.left);
        int right = root.left == null ? 0 : dfs2(val, root.right);
        return left + right;
    }
    public boolean makesquare(int[] matchsticks) {
        int sum = Arrays.stream(matchsticks).sum();
        if(sum%4 != 0 || matchsticks.length<4) return false;
        int length = sum/4;
        Arrays.sort(matchsticks);
        if(matchsticks[0]>length) return false;
        return dfs3(matchsticks,matchsticks.length-1,new int[4],length);
    }

    private boolean dfs3(int[] matchsticks, int index, int[] val, int length) {
        if(index == -1) return true;
        for (int i=0;i<4;i++){
            if(val[i] + matchsticks[index]>length) continue;
            val[i] += matchsticks[index];
            if(dfs3(matchsticks,index-1,val,length))return true;
            val[i] -= matchsticks[index];
        }
        return false;
    }

    public int numUniqueEmails(String[] emails) {
        Set<String> set = new HashSet<>();
        for (String email:emails){
            String[] split = email.split("@");
            if(split[0].contains("+")){
                int i = split[0].indexOf('+');
                split[0] = split[0].substring(0, i);
            }
            set.add(split[0].replace(".","")+split[1]);
        }
        return set.size();
    }

    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = Arrays.stream(piles).max().getAsInt(), mid = 1;
        while (l < r) {
            mid = l + (r - l >> 1);
            int time = getTime(piles, mid);
            if (time < h) r = mid; // 表示可以在h小时内吃完，说明mid值满足情况，那么在左区间内寻找更小的mid
            else l = mid + 1; // 表示mid值太小，在h小时内吃不完，那么在右区间内寻找更小的mid来在h时间内吃完所有香蕉
        }
        return l;
    }

    private int getTime(int[] piles, int mid) {
        int sum = 0;
        for (int pile : piles) {
            int cur = pile % mid == 0 ? pile / mid : pile / mid + 1;
            sum += cur;
        }
        return sum;
    }

    public boolean isBoomerang(int[][] points) {
        int a = points[1][1]-points[0][1];
        int b = points[1][0]-points[0][0];
        int c = points[2][1]-points[1][1];
        int d = points[2][0]-points[1][0];
        return a*d != c*b;// 十字相乘
    }
    //遍历字符串，找到一个分界点，使得该分界点之前1的个数和分界点之后0的个数之和最小
    public int minFlipsMonoIncr(String s) {
        int[] pos = new int[2];
        int zeroCount = 0;
        char[] chars = s.toCharArray();
        for (char ch:chars){
            if(ch == '0') zeroCount++;
        }
        int ret = zeroCount;
        for (char ch:chars){
            pos[ch-'0']++;
            ret = Math.min(ret,pos[1]+zeroCount-pos[0]);
        }
        return ret;
    }
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> list = new ArrayList<>();
        char[] patterChars = pattern.toCharArray();
        int[] pos = new int[26];
        for (String word:words){
            Map<Character,Character> map = new HashMap<>();
            char[] wordChars = word.toCharArray();
            boolean flag = true;
            Arrays.fill(pos,0);
            for (int i=0;i<wordChars.length;i++){

                if(map.containsKey(patterChars[i])){
                    if(!map.get(patterChars[i]).equals(wordChars[i])){
                        flag = false;
                        break;
                    }
                }else {
                    if(pos[wordChars[i]-'a'] != 0){
                        flag = false;
                        break;
                    }
                    map.put(patterChars[i],wordChars[i]);
                }
                pos[wordChars[i]-'a'] = 1;
            }
            if(flag) list.add(word);
        }
        return list;
    }

    public int heightChecker(int[] heights) {
        int ret = 0;
        int[] pos = Arrays.copyOf(heights, heights.length);
        Arrays.sort(pos);
        for (int i=0;i<heights.length;i++){
            if(heights[i] != pos[i]) ret++;
        }
        return ret;
    }

    public int[] findDiagonalOrder(int[][] mat) {
        int r = mat.length,c = mat[0].length;
        int[] ret = new int[r*c];
        int index = 0,curX,curY;
        for (int i=0;i<r+c-1;i++){
            if(i%2 == 1){
               curX = i<c?0:i-c+1;
               curY = i<c?i:c-1;
               while (curY >= 0 && curX < r ){
                   ret[index++] = mat[curX][curY];
                   curY--;
                   curX++;
               }
            }else{
                curX = i<r? i:r-1;
                curY = i<r? 0 :i-r+1;
                while (curX >= 0 && curY < c ){
                    ret[index++] = mat[curX][curY];
                    curX--;
                    curY++;
                }
            }
        }
        return ret;
    }
    public int findPairs(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int ret = 0;
        for (int num:nums){
            if(map.containsKey(num)) {
                if(k==0 && map.get(num) == 1) ret++;
                map.put(num,map.getOrDefault(num,0)+1);
                continue;
            }
            ret += (map.containsKey(num-k)?1:0) + (map.containsKey(num+k)?1:0);
            map.put(num,map.getOrDefault(num,0)+1);
        }
        return ret;
    }
    public void duplicateZeros(int[] arr) {
        for (int i=0;i<arr.length;i++){
            if(arr[i] == 0){
                int index = arr.length-1;
                while (index>i){
                    arr[index] = arr[index-1];
                    index--;
                }
                i++;
            }
        }
    }

    int max = Integer.MIN_VALUE;
    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        dfs4(root,map);
        List<Integer> ret = new ArrayList<>();
        for (Integer key:map.keySet()){
            if(map.get(key) == max){
                ret.add(key);
            }
        }
        return ret.stream().mapToInt(Integer::intValue).toArray();
    }

    private int  dfs4(TreeNode root, Map<Integer, Integer> map) {
        if(root == null) return 0;
        root.val += dfs4(root.left, map)+dfs4(root.right, map);
        map.put(root.val,map.getOrDefault(root.val,0)+1);
        max = Math.max(max,map.get(root.val));
        return root.val;
    }
    class Node1 {
        public int val;
        public Node1 next;

        public Node1(int _val) {
            val = _val;
        }

        public Node1(int _val, Node1 _next) {
            val = _val;
            next = _next;
        }
    };
    public Node1 insert(Node1 head, int insertVal) {
        if(head == null) return new Node1(insertVal);
        Node1 temp = head;
        Node1 maxNode = temp;
        do{
            temp = temp.next;
            if(temp.next.val<temp.val){
                maxNode = temp;
                break;
            }
        }while (temp != head);
        if(insertVal>maxNode.val){
            Node1 newNode = new Node1(insertVal,maxNode.next);
            maxNode.next = newNode;
            return head;
        }
        while (true){
            if(maxNode.next.val>=insertVal){
                Node1 newNode = new Node1(insertVal,maxNode.next);
                maxNode.next = newNode;
                break;
            }
        }
        return head;
    }

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.isEmpty()){
            int curLength = queue.size();
            int max = Integer.MIN_VALUE;
            for (int i=0;i<curLength;i++){
                TreeNode poll = queue.poll();
                max = Math.max(max,poll.val);
                if(poll.left!=null) queue.offer(poll.left);
                if(poll.right!=null) queue.offer(poll.right);
            }
            ret.add(max);
        }
        return ret;
    }

    public int minCost(int[][] costs) {
        int len = costs.length-1;
        for (int i=1;i<=len;i++){
            costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][0],costs[i-1][1]);
        }
        return Math.min(Math.min(costs[len][0],costs[len][1]),costs[len][2]);
    }

    ;
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        char[] chars = longUrl.toCharArray();
        for (int i=0;i<chars.length;i++){
            chars[i] = (char)(chars[i]+1);
        }
        return new String(chars);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        char[] chars = shortUrl.toCharArray();
        for (int i=0;i<chars.length;i++){
            chars[i] = (char)(chars[i]-1);
        }
        return new String(chars);
    }
    public int numPrimeArrangements(int n) {
        int ret = 0;
        for (int i=2;i<=n;i++){
            if(isPrime(i)) ret++;
        }
        return factorial(ret,n-ret);
    }

    private int factorial(int count,int count2) {
        int mod = 1000000007;
        long ret = 1;
        for (int i=count;i>1;i--){
            ret = ret*i%mod;
        }
        for (int i=2;i<=count2;i++){
            ret = ret*i%mod;
        }
        return (int) ret;
    }

    private boolean isPrime(int num){
        for (int i=2;i<=num/2;i++){
            if(num%i == 0) return false;
        }
        return true;
    }

    @Test
    public  void main() {
        System.out.println(numPrimeArrangements(16));
        //duplicateZeros(new int[]{1,0,2,3,0,4,5,0});
        //findPairs(new int[]{1, 3, 1, 5, 4},0);
        //findDiagonalOrder(new int[][]{{1,2,3},{4,5,6},{7,8,9}});
        //isBoomerang(new int[][]{{73,31},{73,19},{73,45}});
        //minEatingSpeed(new int[]{30,11,23,4,20},7);
        //numUniqueEmails(new String[]{"test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"});
        //makesquare(new int[]{1,1,2,2,2});
        //System.out.println(construct(new int[][]{{0,1},{1,0}}));
        //BigDecimal bigDecimal = new BigDecimal(100);
        //BigDecimal bigDecimal2 = new BigDecimal(15);
        //System.out.println(bigDecimal.subtract(bigDecimal2));
        //isAlienSorted(new String[]{"apple","app"},"abcdefghijklmnopqrstuvwxyz");
        //minMoves2(new int[]{2,9,-1,-5,100});
        //findSubstringInWraproundString("abcdfffcdef");
        //findClosest(new String[]{"I","am","a","student","from","a","university","in","a","city"},"a","student");
        //validIPAddress("2001:0db8:85a3:0:0:8A2E:0370:7334:");
        // 1152921504606846975
        //System.out.println(new BigInteger("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16).toString());
    }

    /**
     * 删除二叉搜索树中的指定节点,情况分析
     * 1.不存在该节点：直接返回原根节点
     * 2.该节点没有子节点：
     * 3.该节点只存在左节点
     * 4.该节点只存在右节点
     * 5.该节点存在左右节点
     *
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode last = new TreeNode(Integer.MAX_VALUE,root,null),curRoot = last;
        while (root != null){
            if(key < root.val){
                last = root;
                root = root.left;
            }else if(key > root.val){
                last = root;
                root = root.right;
            }else{
                TreeNode node = null;
                if(root.left!=null && root.right == null){
                    node = root.left;
                }else if(root.left == null && root.right != null){
                    node = root.right;
                }else if(root.left != null && root.right != null){
                    TreeNode right = root.right;
                    while (right.left!=null){
                        right = right.left;
                    }
                    right.left = root.left;
                    node = root.right;
                }
                if(root.val> last.val) last.right = node;
                else last.left = node;

                root = null;
            }
        }
        return curRoot.left;
    }

}
